'''
快速排序（Quick Sort）是一种常见的排序算法，基于分治的思想，
通过一趟排序将待排序的数据分割成独立的两部分，
其中一部分的所有数据都比另外一部分的所有数据都小，
然后再按照此方法分别对这两部分数据进行快速排序，整个排序过程递归进行，
以此达到整个数据变成有序序列的目的。

快速排序的实现步骤如下：
1. 选取基准元素（pivot），一般选取第一个元素或最后一个元素；
2. 将数组中小于等于基准元素的数放到左边，大于基准元素的数放到右边；
3. 对左右两部分分别重复步骤1和步骤2，直到每个子区间只有一个元素。
'''



'''
参数arr是待排序的数组。如果数组长度小于等于1，则不需要排序，直接返回该数组。
否则，取第一个元素作为pivot，将数组分成小于等于pivot的left数组和大于pivot的right数组。
然后，对left数组和right子数组递归执行quick_sort函数，直到数组长度为1或0，
然后将left数组、pivot和right数组合并返回。
'''


def quick_sort(arr):
    #如果数组为空或只有一个元素，返回该数组
    if len(arr) <= 1:
        return arr
    else:
        #选择数组中的一个元素作为枢轴(pivot)
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            #将数组分成两部分：小于等于pivot的元素和大于pivot的元素
            if arr[i] <= pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        #合并两个子数组和pivot  对两个子数组递归地执行步骤2和步骤3，直到子数组长度为1或0
        return quick_sort(left) + [pivot] + quick_sort(right)

arr = [2,3,2,24,25,56,3,32,7,8,534,6,4,7]
print("排序后的数组：",quick_sort(arr))
